import java.util.Random;

public class QSort {
    private Random random = new Random();

    public void qSort(int v[], int l, int u) {
        if (l < u) {
            int m = partition(v, l, u);
            qSort(v, l, m - 1);
            qSort(v, m + 1, u);
        }
    }

    private int partition(int v[], int l, int u) {
        if (l >= u) {
            return -1;
        }
        swap(v, l, randInt(l, u));
        int t = v[l];
        while (l < u) {
            while (l < u && v[u] >= t) {
                u--;
            }
            v[l++] = v[u];
            if (l > u) {
                l--;
                break;
            }
            while (l < u && v[l] <= t) {
                l++;
            }
            v[u--] = v[l];
        }
        v[l] = t;
        return l;
    }

    private int randInt(int l, int u) {
        return random.nextInt(u - l + 1) + l;
    }

    private void swap(int v[], int a, int b) {
        int temp = v[a];
        v[a] = v[b];
        v[b] = temp;
    }

    public void display(int v[]) {
        for (int n : v) {
            System.out.print(n + "  ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int v[] = { 2, 1, 3, 6, 3, 4, 10, 14 };
        QSort qsort = new QSort();
        System.out.print("排序前：");
        qsort.display(v);
        qsort.qSort(v, 0, v.length - 1);
        System.out.print("排序后：");
        qsort.display(v);
    }
}
